package chapter03_binaryTree;

/**
 * 描述：
 * Morris遍历，时间复杂度O(n)，空间复杂度O(1)
 *      将每颗子树的最右结点的右指针指向当前子树的根结点，这样就可以从下层结点回到上层结点
 *      1.找到当前结点的左子树的最右结点
 *      2.  判断当前结点cur的左子树的最右结点cur1的right指针是否指向cur
 *              1)如果不指向说明第一次来到cur结点，将cur1的right指针指向cur
 *              2)如果指向说明cur的左子树已经遍历完成，第二次来到cur，此时需要将cur1的right指针指向null恢复原来的结构
 *      3.如果步骤2中走的是1）则继续则将cur指向cur的left，则继续步骤1，继续构建左子树中的所有子树的结构
 *         如果步骤2中走的是2）则说明当前cur的左子树已经遍历完成，需要将cur指向cur.right，继续步骤1构建右子树的结构
 *      中序遍历：在2.2）步骤后，当cur要向cur.right移动之前打印
 *      前序遍历：在3.1）步骤中，当cur要向cur.left移动之前打印
 *      后序遍历：在3.2）第二次来到cur的时候，逆序打印以cur.left为根结点的树的右边界
 *
 * @author hl
 * @date 2021/5/5 8:51
 */
public class MorrisOrder {

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        MorrisOrder morrisOrder = new MorrisOrder();
        PrintTree printTree = new PrintTree();
        printTree.printTree(head);
        morrisOrder.morrisIn(head);
        morrisOrder.morrisPre(head);
        morrisOrder.morrisPos(head);
    }

    public void morrisIn(Node root) {
        if (root == null) {
            return;
        }
        Node cur1 = root;
        Node cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            //处理左子树
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    //第一次来到cur1的左子树的最右结点，将左子树的最右结点的right指向cur1
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    //将左子树的每个子树的这样设置
                    continue;
                } else {
                    //走完cur1的左子树，回到cur1
                    cur2.right = null;
                }
            }
            System.out.print(cur1.val + ",");
            cur1 = cur1.right;
        }
        System.out.println();
    }

    public void morrisPre(Node root) {
        if (root == null) {
            return;
        }
        Node cur1 = root;
        Node cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            //处理左子树
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    //第一次来到cur1的左子树的最右结点，将左子树的最右结点的right指向cur1
                    cur2.right = cur1;
                    System.out.print(cur1.val + ",");
                    cur1 = cur1.left;
                    //将左子树的每个子树的这样设置
                    continue;
                } else {
                    //走完cur1的左子树，回到cur1
                    cur2.right = null;
                }
            }else{
                System.out.print(cur1.val + ",");
            }
            cur1 = cur1.right;
        }
        System.out.println();
    }

    public void morrisPos(Node root) {
        if (root == null) {
            return;
        }
        Node cur1 = root;
        Node cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            //处理左子树
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    //第一次来到cur1的左子树的最右结点，将左子树的最右结点的right指向cur1
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    //将左子树的每个子树的这样设置
                    continue;
                } else {
                    //走完cur1的左子树，回到cur1
                    cur2.right = null;
                    printEdge(cur1.left);
                }
            }
            cur1 = cur1.right;
        }
        printEdge(root);
        System.out.println();
    }

    private void printEdge(Node node) {
        Node tail = reverseEdge(node);
        System.out.print(tail.val + ",");
        while(tail.right != null){
            System.out.print(tail.right.val + ",");
            tail = tail.right;
        }
        reverseEdge(tail);
    }

    private Node reverseEdge(Node node) {
        Node cur = node;
        Node pre = null;
        Node next = null;
        while(cur != null){
            next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
